COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	PROPOSAL TO NSF  -  (Bernie Chern).
C00006 00003	iv. Object Representation from Physical Measurement,
C00010 00004	2. WHAT WE PROPOSE TO DO.
C00020 00005	 Elements of a Geometric Modeling System (continued).
C00025 00006	 Elements of a Geometric Modeling System (continued).
C00030 00007	   Itemized Shopping List.
C00034 00008	3. PREVIOUS WORK AT STANFORD.
C00037 00009	4. RELATION TO WORK DONE ELSEWHERE.
C00042 00010	5. FACILITIES AT STANFORD A.I. LAB
C00043 ENDMK
C⊗;
PROPOSAL TO NSF  -  (Bernie Chern).
	Principal Investigator - John McCarthy.
	Co Principal Investigator - Bruce Baumgart.

	This is a  request for a grant of  XXX to support a  two year
research  program  in  computer  aided  mechanical  drawing of  three
dimensional objects.

OUTLINE
	1. Ideas and work already done.
	2. What we propose to do.
	3. Previous work at Stanford.
	4. Relation to work done elsewhere.
	5. Facilities at Stanford AI Lab.
	6. Budget.

1. IDEAS AND WORK ALREADY DONE.

	The proposed work  is based on  the following ideas  and work
already done:

i. Explicit Object Representation.

	An effective way  of obtaining drawings of  three dimensional
objects is  to derive the drawing from  an explicit computer model of
the three  dimensional  object.   The  orthographic,   isometric  and
perspective  projections of  the objects  are obtained  automatically
from the  three dimensional description; with the hidden lines of the
object either eliminated, dashed or  thinned;   and  with  the appro-
priate labels, dimensions, comments, and  arrowheads indicated.

ii. Object Representation from Logical Description.

	One convenient  way of making  an explicit computer  model of
an object is  to simulate the process of building the object; that is
the  description  of   how  to  build  an   object  is  an   implicit
representation of the  object.  For example it is  more convenient to
describe  Figure-1 implicitly as  a cube with a  regular five pointed
star shaped hole cut through it,  than as a list of the locii  of all
its vertices.

iii. Language Extension.

	Rather than developing  new languages for  geometric modeling
and  mechanical drawing,  we believe  it  is best  to extend  the old
languages: FORTRAN,   ALGOL and  LISP.   The elements  of a  language
extension  include a  new data  types for  the language,  general low
level  primitives  for  manipulating  the  new  data  types,   and  a
convenient set of particular high level operations.   The division of
the work  into high  level operations defined  in terms of  low level
primitives is an  important part  of the design  because it  isolates
the data structure manipulating code.
iv. Object Representation from Physical Measurement,

	Another way to  get an explicit  computer model of  an object
is to derive  it from measurements made on an actual physical object,
2D drawings, or pictures.  For example, the physical object  might be
a clay  or wood model  of the thing  begin designed. We  believe that
only  the  lack of  appropriate  software  is preventing  the  use of
television cameras as  an inexpensive, accurate, and  automatic means
of entering graphical data into a computer.

V. Prejudice against pens for graphics input.

	We believe  that the  use of pens:  light pens,   sonic pens,
Rand tablets,  Lincoln Wands, mechanical pens, joy sticks and so  on;
can be  replaced to  advantage by  keyboard and  video input.  First,
adequate keyboard  edit,  control and  language conventions should be
developed for cases where the pen  is used as a glamorized stick  for
pushing  buttons. Pen  based editing  systems require  a keyboard  or
button  box in  any  event,   so we  argue that  an operator  who can
control and alter a drawing with his hands always  in the locality of
the keyboard will  be more efficient than an operator  who has to use
both a keyboard  and a  pen. Second,  one current  justifible use  of
pens  and  tablets  is for  tracing  an  existing  drawing  into  the
computer;  we  believe  that  video  software  can  be  developed  to
automate this operation.

vi. Mechanical Simulation.

	Information such  as the  degrees of  freedom  of motion  are
included in  the object description and  can be used to  get pictures
of  objects  in  different  positions,   as  is  demonstrated  in the
(enclosed) flip book  animation of a  mechanical arm turning a  block
over. Mechanical  information can also be used  to constain the shape
of a part  in its  desired place; or  to find  the space  potentially
occupied by a moving part.

vii. Photomeric Simulation.

	Photometric information  such as the  location and  nature of
light  sources and  the light scattering  properties of  the objects'
surfaces can be included in the  model and used to compute the  video
appearance of solid opaque objects.
2. WHAT WE PROPOSE TO DO.

	We  propose to  represent  and simulate  solid  objects in  a
computer for  the sake of mechanical design,   mechanical drawing and
robotics.  Our two year goal will be to automate as much  as possible
the task of  creating and altering three  dimensional data structures
from  which mechanical drawings can be  derived; this work would also
be  a step  towards  solving  the problem  of  representing  physical
objects for  a robot.   The overall project  to date has  been called
"geometric modeling" a term which we  use to refer to our  particular
combination of  computer graphics,   physical world modeling,   image
processing  and geometry.   Accordingly, the  details of the  work we
propose doing will be presented  in terms of the elements  comprising
a Geometric Modeling System,  GMS.  (The reader interested only in an
itemized  list of project goals is advice to  skip to the end of this
section).

	Like a  computer,   the  four main  elements  of a  geometric
modeling system are  memory, process, input and output. Starting with
memory, there are the problems  of representation (how to describe  a
physical object); accessing (how to  find a particular description by
name,   by  location, or  by whether  it is  currently in  view); and
efficiency (how to  keep the size  of storage space  down and how  to
dynamically allocate fast and slow memory resources).
	
	The currently  implemented explicit object  representation is
based on polyhedron  models of solid rigids objects.  A simple object
called a body is defined by a surface shell composed of  faces, edges
and vertices that satisfies  the Euler equation, V - E +  F = 2; such
polyhedron  bodies  are  combined  to  form  compound  objects.    At
present, curved objects  are represented by approximating  them using
a  polyhedron  composed of  a  sufficient  number  of flat  polygonal
faces. We propose developing a representation for curved objects,  by
elaborating  our   polyhedrons  to  include   faces  which   are  not
necessarily  flat but  are  defined by  a function.    These non-flat
polyhedrons will  be  called manifolds,   and  additional  processors
would be developed to generate, alter, smooth, and display them.

	A  final representation  issue we  would study  is that  of a
format  for communication  of three dimensional  models between alien
modeling systems.  We  believe that  developing  a three  dimensional
standard format  for everybody is  very premature; and  that the best
one  project   can   realistically   expect   to   achieve   (towards
standardization)  is to  establish and  promulgate  a reasonible  way
that alein systems may communicate with the local system.
 Elements of a Geometric Modeling System (continued).

	The  usual  input  devices to  a  geometric  modeling  system
include  keyboards,   light-pens,  joy-sticks,  buttons,  cameras and
film scanners; of which  the most important  to this proposal is  the
keyboard because it is currently  the best device for language input.
Indeed,    we  believe we  can  demonstrate that  a  system  based on
keyboards can do geometric  control and editing better than  a system
based on both a light pen and a keyboard.

	To  repeat,   rather  than   developing  new  languages   for
geometric modeling and  mechanical drawing,  we propose extending the
programming languages: FORTRAN,  ALGOL  and LISP.  The elements of  a
language  extension  include new  data  types  (the "memory"  of  our
system);  a general purpose micro language  level of primitives and a
special purpose macro language level of operations.

	The micro level of language extension is  composed of a small
set of  primitive functions that invoke  the only subroutines allowed
to directly create  and alter the data  structure. All the  geometric
processors,   editors, input,  output and higher  language operations
are  implemented in terms of these fewer  than fifty primiitves.  The
resaon for having a two level system, is to  isolate and minimize the
amount of  code that is necessarily  dependent on the  details of the
data format.   Furthermore, it  is possible  to construct  primitives
that are complete  and general with repect to  fundamental principles
in polyhedron  topology and geometry. For example,  we now have a set
of Euler primitives  that can generate  any Eulerian polyhedron  (and
only Eulerian  polyhedra); as well  as a set of  Euclidean primitives
for  applying the group of Euclidean  transformations. With more good
luck,  we  intend  to  isolate  sets  of  primitives  for  mechanics,
manifolds, and image forming.

	The  macro  level  of  language  extension  is  comprised  of
operations that make  it convenient to simulate building a mechanical
model of an  object. The  present macro level  includes an  operation
for "sweeping" edges into faces,  and faces into solids; an operation
for  "glueing" surfaces together; an  operation for passing "cutting"
planes thru an  object; and  a most powerful  trio of operations  for
forming  the volume  set union,  intersection and  difference  of two
given polyhedrons. Since polyhedrons can be taken as either  bounding
a finite  solid volume  or a finite  empty volume;  we have found  it
convenient  to draw some  objects indirectly by  building their holes
and intersecting  the holes with  their simple  outer shape.  Further
macro operations  we propose to  code would include  more "imaginery"
ones  for bending,  constraining, filling,  enveloping, and expanding
upon a  skeleton; as well  as some  more "realistic" operations  that
would model  regular machine  shop tools such  as a lathe,  punch and
milling machine;  and machine  building  processes such  as  welding,
fastening and assembly.
 Elements of a Geometric Modeling System (continued).

	A  third kind  of  language is  that  provided for  edit  and
control.    The  main  differences  between  a  powerful  interactive
graphics editor  and  a  powerful  interactive  graphics  programming
language  is  that  an  editor  carries  along  its  working  context
automatically  so that  most  arguments and  data do  not have  to be
explicitly named because they happen to be "at the  top of the stack"
and  are visibly intensified  or otherwise  indicated on  the display
screen. The advantage of the interactive  editor is that the user  is
relieved of  having to  coin and  call names  of things, however  the
disadvantage  is that he  can not  develope subroutines of  the power
available in  a  programming  language which  provides  notation  for
procedures, arguments, and variables. Rather  than lose the speed and
convenience  of editing,  we  plan to  keep the  programming language
level distinct from the control and edit language.

	Besides language inputs,  a  geometric modeling system should
have  a way of  reading data that  is already in  graphical form. For
such graphical  input,   we  propose  using  a televsion  camera  and
believe that  a system with  a few video image  processing primitives
can  allow using  video as a  routine computer  graphics input media.
For example, we already have developed video  intensity contouring to
rapidly  provide  the edges  of  an image  in  a  form available  for
graphics editing.

	The third main element of a geometric  modeling system is the
geometric  processors.   There are  language processors,   mechanical
simulators,   locus solvers,   image  analysis  and image  synthesis,
including  the process  most  peculiar to  three dimensional  drawing
which  is hidden  line (and  surface) elimination.   We  have several
implementations  of   each  of   several   hidden  line   elimination
algorithms; and  we have reason to  believe that further  work on our
most recent design  will yield  a hidden eliminator  that can  handle
curved  objects,    generate shadows,    use  the  coherence  between
successive  images,    and  still  be  fast without  special  purpose
hardware. Since the purpose  of the processors just mentioned  should
be sufficiently  clear we shall  skip detailing their  algorithms and
implementation, although  this will comprise the bulk of the work and
publication we propose to do.

	The fourth  and final  element of  a modeling  system is  the
output,  which includes dynamic CRT  display, video display, hardcopy
graphics, as well as  magnetic tape. Although mundane, the  numerical
object  descriptions on  conventional  (non  display) computer  media
like  magnetic   tape  is  important  in  making  the  output  of  an
interactive   display  system   available   for   further   automatic
processing.


   Itemized Shopping List.

	Ignoring the overall system organization and fine details,
the goals of the proposed project are summarized in the following
shopping list:

Items partially in hand.

	1. Representation of solid rigid three dimensional polyhedra.
	2. Language extension of geometric primitives.
	3. Language extension of object building operations.
	4. Polyhedron object hidden line eliminator.
	5. Geometric editor.

Items within one year's work.
	
	6. Generation of mechanical drawings from geometric models.
	7. Representation for curved objects.
	8. Representation for flexible objects.
	9. Video acquisition of two dimensional  drawings.
	10. Mechanical simulation and animation.

Second year and elective Items.

	11. Generation of high quality mechanical drawings, such as
   	    assembly drawings and cut away layout drawings.
	12. Development of a remote display terminal version.
	13. Development of a standard FORTRAN version.
	14. Mechanical drawings for a special area of engineering;
	    (pipefitting, screw threading, mining, or whatever).
	15. Hidden line elimination for curved objects.

Basic research items.

	16. Video acquisition of three dimensional objects.
	17. Photometric simulation - shadows, multiple light sources;
	    for generation of high quality video appearance.

	Substantial work  has  already been  done on  the first  five
items listed; so  that the most pessimistic and conservative estimate
of our potential achivevements for the next two years  should include
the documentation,  publication and  elaboration of the research work
already   done.     Our  intermediate   expectations  include  making
considerable progress and  original contribution with respect  to the
first five items as well  as being able to get a substantial start on
items numbered six  through ten;  as well as  doing one  of the  five
items numbered  eleven  through fifteen.   Finally,   our  optimistic
expectation  would be to  finish everything though  item fifteen, and
to have  started work  on getting  a system  that  could reduce  live
video input into  a mechanical model and that  could output realistic
looking video from a mechanical model.
3. PREVIOUS WORK AT STANFORD.

	This proposal  is based  on work  by Bruce  G. Baumgart as  a
graduate  student. Mr. Baumgart expects  to complete his dissertation
entitled "Geometric Vision" in December  1973 and will continue as  a
research associate on receiving his degree.

	This work includes GEOMED,   a Geometric Editor,  which would
be  the  prototype of  the mechanical  drawing  system we  propose to
build.    GEOMED  is  a  3D  drawing  program  (controled  solely  by
keyboard);  that  can  construct  arbitrary  polyhedral  objects  and
display them  with  hidden lines  eliminated.   GEOMED  also  accepts
CRE-images  (explained  below)  and  can   form  a  polyhedron  model
consistent with such images.

	The  subroutines  and  data structures  of  GEOMED  have been
embedded in LISP  and SAIL  (Stanford Algol) to  provide a  geometric
language for physical world  modeling and physical action simulation.
The  embedded  versions  of  GEOMED  fall  short  of  being  language
extensions in that adequate syntax and flexible  memory allocation is
currently lacking.

	The image processing  part of Mr.  Baumgart's  work lies in a
program named  CRE,   standing  for Contour,    Region,   Edge  image
representation.    CRE  converts a  sequence  of  digital  television
images  into  a contour  edge  data structure  for  interpretation by
other programs. Finally, there is  TVFONT, which is a version of  CRE
for  making type  font  bit  arrays from  television  images, or  for
rescaling existing fonts.
4. RELATION TO WORK DONE ELSEWHERE.

	The work  proposed here has  been strongly influenced  by the
pioneering computer graphics  work of Larry Roberts, Steven Coons and
Ivan  Sutherland  done  at  Massachusetts  Institute  of  Technology,
Lincoln  Laboratory, and  Harvard  University; as  well  as the  more
recent  work of Sutherland, Evans,  Warnock, Watkins, X,  Y, and Z at
the University of Utah.  In fact, Mr. Baumgart did  his undergraduate
thesis (at Harvard, 1968)  with Prof. Sutherland, on development of a
three dimensional  display  system  which was  subsquently  moved  to
Utah. However, recent  research work at  Utah has been  directed more
to  the development of  special purpose display  hardware rather than
to the representation and input of three dimensional models.

	Another major  influence on  the proposed  work has been  the
research  in  Artificial Intelligence,  Computer  Vision, Programming
Languages   and   Time   Sharing   done   at   Stanford   University,
Massachusetts Institute of Technology and Stanford Research Institute.

	Several interactive  three dimensional drawing  programs have
been  written over  the last  ten years; however  the genre  is still
steeped in  poorly understood  data structures  and algorithms,  with
problems  compounded  by  changing display  hardware  technology  and
changing system environments.

3D sketchpad
X's thing at the University of Illinois.
Appel with IBM at Yorktown.
Lockheed
General Electric - flight simulators & display hardware.
Military - flight simulators.
NASA

Distinguish commerical 2D graphics and  automatic drafting (Cal Comp,
Gerber,  etc) from 3D  design and mechanical  drawing (General Motors
Research Laboratories - DAC System).

	Finally, there  are many  commercially available  engineering
programs   that   generate   mechanical   drawings   for   particular
applications.  For  example,  the  Control Data  Corporation,  has  a
system  that  does  structural  steel  detailing  and  that  produces
graphics  in accord with the drawing  standards of the American Steel
Association.   Such special  purpose drawing  programs require  input
decks specifying  the exact shape,   dimensions and  location of each
steel beam and are  larger prepared by  hand. A flexible  interactive
three  dimensional  design  program,  such  as  the  one  we  propose
creating,   would   be   able  to   allow   interactive   design  and
specification  of  steel  structures;  programing  of  operators  for
handling  steeling  structures;  and (in  effect)  FORMAT  statements
which would  allow outputing the special particular data required
by an existing programs.
5. FACILITIES AT STANFORD A.I. LAB

	1. Time Sharing System - its relevance.
	2. III displays
	3. Data Disc displays.
	4. XGP printer
	5. Output for FR-80.

6. BUDGET

	1. Baumgart
	2. A programmer.
	3. A graduate student.
	4. Two high quality display terminals.
	   e.g. Systems concept's best.